package bgai.ai.minimax;

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;


// http://aihw2.googlecode.com/svn-history/r32/trunk/AI_Hw2/AI_Hw2/Expectimax.cpp
public class Search {

	/** numero di nodi visitati (nodi intermedi + nodi foglia) */
	private static long numNodes;
	/** numero di nodi su cui viene calcolata l'euristica (nodi foglia == nodi terminali) */
	private static long numEval;

	/** true per NON stampare output di debug */
	private static boolean silentDebug= true;

	/** true per NON stampare alcun tipo di output */
	private static boolean silent= false;
	
	/** Tempi di esecuzione di best-move per il player MAX */
	private static Vector<Long> maxTimeStat= new Vector<Long>(100);
	/** Tempi di esecuzione di best-move per il player MIN */
	private static Vector<Long> minTimeStat= new Vector<Long>(100);
	/** Numero di nodi visitati da best-move per il player MAX */
	private static Vector<Long> maxNodesStat= new Vector<Long>(100);
	/** Numero di nodi visitati da best-move per il player Min */
	private static Vector<Long> minNodesStat= new Vector<Long>(100);
	
	/** XXX profondita' del nodo radice */
	private static int rootDepth;
	
	/** XXX true per usare il failsoft */
	public static boolean FAIL_SOFT= false;
	/** XXX true per usare star2, false per usare star1 */
	public static boolean STAR2= true;
	/** XXX Disabilita nello star2 il cutoff nella fase di probing */
	public static boolean DISABLE_PROBING_CUTOFF = false;
	/** XXX Disabilita nello star2 lo sfruttamento della fase di probing per il calcolo di A e B */
	public static boolean DISABLE_PROBING_AB = false;
	
	private static String tabs(int depth) {
		String str= "";
		
		for (int k=depth; k<rootDepth; k++) {
			str+= "\t";
		}
		
		return str;
	}
	
	public static MoveEvent bestMoveExpectimax(Evaluator eval, Board board, int depth) {
		// siamo in un nodo MIN/MAX
		
		String name= "expec";
		
		long startTime = System.nanoTime();
		
		boolean isMaxNode;

		switch (board.getBoardType()) {
		case MAX:
			isMaxNode= true;
			break;
		case MIN:
			isMaxNode= false;
			break;
		default:
			throw new RuntimeException("bestMove() e' richiamabile solo su nodi "
		+BoardType.MIN+" o "+BoardType.MAX+", ma era "+board.getBoardType());
		}

		if (!silentDebug) System.out.println("bestMove - nodo="+board+", tipo="+board.getBoardType()+": ricerca della miglior mossa (depth="+depth+")");
		
		List<? extends MoveEvent> moveEvents = board.moveEvents(eval);
		if (!silent) System.out.println(name+": "+"Numero di mosse possibili: "+moveEvents.size());
		MoveEvent best= null;
		
		double bestScore;
		if (isMaxNode) bestScore= Double.NEGATIVE_INFINITY;
		else bestScore= Double.POSITIVE_INFINITY;

		double alpha= eval.lowerBound();
		double beta= eval.upperBound();
		
		numNodes= 1; // esamino anche il nodo radice
		numEval= 0;
		int moveInd=0;
		int moveSize= moveEvents.size();
		rootDepth= depth;
		//System.out.println("Branching factor root: "+moveEvents.size());
		for (MoveEvent me : moveEvents) {
			moveInd++;
			if (!silentDebug) System.out.println("bestMove - nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": eseguo mossa ("+moveInd+"/"+moveSize+") "+me);
			
			Board succ= board.successor(me);
			double d= expectimax(eval, succ, depth-1, !isMaxNode);
			
			if (!silent) System.out.println("bestMove - nodo="+board+", tipo="+board.getBoardType()+", depth="+depth
					+": mossa ("+moveInd+"/"+moveSize+") "+me+", score="+d);
			if (!silentDebug) System.out.println();
			

			if (isMaxNode) {
				
				// massimizzo
				if (d>bestScore) {
					best= me;
					bestScore= d;
					alpha= bestScore;
				}
				
				if (alpha >= beta) {
					break;
				}
				if (bestScore == eval.upperBound()) {
					break;
				}
				
			} else {
				
				// minimizzo
				if (d<bestScore) {
					best= me;
					bestScore= d;
					beta= bestScore;
				}
				
				if (alpha >= beta) {
					break;
				}
				if (bestScore == eval.lowerBound()) {
					break;
				}
				
			}
			
		}
		
		long endTime = System.nanoTime();

		if (!silent) System.out.println(name+": "+"Tempo di esecuzione bestMove: " + (double)(endTime - startTime)/1000000.0 +" ms");
		if (!silent) System.out.println(name+": "+"Numero di nodi esaminati: "+numNodes);
		if (!silent) System.out.println(name+": "+"Numero di nodi terminali (valutati con euristica): "+numEval);
		if (isMaxNode) {
			maxTimeStat.add(endTime - startTime);
			maxNodesStat.add(numNodes);
		} else {
			minTimeStat.add(endTime - startTime);
			minNodesStat.add(numNodes);
		}
		
		if (!silentDebug) System.out.println("bestMove - nodo="+board+", tipo="+board.getBoardType()+": la miglior mossa e' "+best + " score " + bestScore);
		
		return best;
	}
	
	public static MoveEvent bestMoveStar(Evaluator eval, Board board, int depth) {
		return bestMoveStar(eval, board, depth, eval.lowerBound(), eval.upperBound());
	}
	
	public static MoveEvent bestMoveStar(Evaluator eval, Board board, int depth, double lower, double upper) {
		// siamo in un nodo MIN/MAX
		
		String name;
		if (STAR2) name= "star2";
		else name= "star1";
		
		long startTime = System.nanoTime();
		
		boolean isMaxNode;

		switch (board.getBoardType()) {
		case MAX:
			isMaxNode= true;
			break;
		case MIN:
			isMaxNode= false;
			break;
		default:
			throw new RuntimeException("bestMoveAlphaBeta() e' richiamabile solo su nodi "
		+BoardType.MIN+" o "+BoardType.MAX+", ma era "+board.getBoardType());
		}

		if (!silentDebug) System.out.println("bestMove - nodo="+board+", tipo="+board.getBoardType()+": ricerca della miglior mossa (depth="+depth+")");
		
		List<? extends MoveEvent> moveEvents = board.moveEvents(eval);
		if (!silent) System.out.println(name+": "+"Numero di mosse possibili: "+moveEvents.size());
		MoveEvent best= null;
		
		double bestScore;
		if (isMaxNode) bestScore= Double.NEGATIVE_INFINITY;
		else bestScore= Double.POSITIVE_INFINITY;
		
		numNodes= 1; // esamino anche il nodo radice
		numEval= 0;
		
		double alpha= lower;
		double beta= upper;

		int moveInd=0;
		int moveSize= moveEvents.size();
		rootDepth= depth;
		for (MoveEvent me : moveEvents) {
			moveInd++;
			
			//alpha= lower; // XXX decommentare per disabilitare aggiornamento di alpha e beta
			//beta= upper; // XXX decommentare per disabilitare aggiornamento di alpha e beta
			
			if (!silentDebug) System.out.println("bestMove - nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": eseguo mossa ("+moveInd+"/"+moveSize+") "+me);
			
			Board succ= board.successor(me);
			double d;
			if (STAR2) {
				if (isMaxNode) d= star2min(eval, succ, depth-1, alpha, beta);
				else d= star2max(eval, succ, depth-1, alpha, beta);
			} else {
				d= star1(eval, succ, depth-1, !isMaxNode, alpha, beta);
			}
			
			if (!silent) System.out.println("bestMove - nodo="+board+", tipo="+board.getBoardType()+", depth="+depth
					+": mossa ("+moveInd+"/"+moveSize+") "+me+", score="+d);
			if (!silentDebug) System.out.println();
			
			if (isMaxNode) {
				
				// massimizzo
				if (d>bestScore) {
					best= me;
					bestScore= d;
					alpha= bestScore;
				}
				
				if (alpha >= beta) {
					break;
				}
				if (bestScore == eval.upperBound()) {
					break;
				}
				
			} else {
				
				// minimizzo
				if (d<bestScore) {
					best= me;
					bestScore= d;
					beta= bestScore;
				}
				
				if (alpha >= beta) {
					break;
				}
				if (bestScore == eval.lowerBound()) {
					break;
				}
				
			}
			
		}
		
		long endTime = System.nanoTime();

		if (!silent) System.out.println(name+": "+"Tempo di esecuzione bestMove: " + (double)(endTime - startTime)/1000000.0 +" ms");
		if (!silent) System.out.println(name+": "+"Numero di nodi esaminati: "+numNodes);
		if (!silent) System.out.println(name+": "+"Numero di nodi terminali (valutati con euristica): "+numEval);
		if (isMaxNode) {
			maxTimeStat.add(endTime - startTime);
			maxNodesStat.add(numNodes);
		} else {
			minTimeStat.add(endTime - startTime);
			minNodesStat.add(numNodes);
		}
		
		if (!silentDebug) System.out.println("bestMove - nodo="+board+", tipo="+board.getBoardType()+": la miglior mossa e' "+best + " score " + bestScore);
		
		return best;
	}
	
	
	/**
	 * 
	 * @param eval euristica
	 * @param board stato
	 * @param depth profondita' di ricerca
	 * @param nextIsMaxNode true se il nodo successivo e' di tipo {@link BoardType.MAX}
	 * @return
	 */
	public static double expectimax(Evaluator eval, Board board, int depth, boolean nextIsMaxNode) {
		numNodes++;
		// siamo in un nodo CHANCE
		if (board.getBoardType()!=BoardType.CHANCE) {
			throw new RuntimeException("expectimax() e' richiamabile solo su nodi "+BoardType.CHANCE+", ma era "+board.getBoardType());
		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": entro nel sottolivello");
		
		if (board.isTerminal() || depth<=0) {
			double ret= eval.evaluate(board, !nextIsMaxNode);
			if (!silentDebug) System.out.println(tabs(depth)+"nodo terminale "+ret);
			numEval++;
			return ret;
		}
		
		List<? extends ChanceEvent> events= board.chanceEvents();
		double sum=0;
		
		//System.out.println("Branching factor chance: "+events.size());
		int moveInd=0;
		int moveSize= events.size();
		for (ChanceEvent ev : events) {
			moveInd++;
			
			if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+(moveInd)+"/"+events.size()+") "+ev);
			
			Board succ= board.successor(ev);
			double score= minimax(eval, succ, depth-1, nextIsMaxNode);
			double prob= ev.probability(); 
			sum += prob * score;
			
			if (!silentDebug) System.out.println(tabs(depth)+"score ("+(moveInd)+"/"+events.size()+") "+ev+" = " + score);
		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(sum));
		return sum;
	}
	
	
	/**
	 * Star1
	 * @param eval euristica
	 * @param board stato
	 * @param depth profondita' di ricerca
	 * @param nextIsMaxNode true se il nodo successivo e' di tipo {@link BoardType.MAX}
	 * @return
	 */
	public static double star1(Evaluator eval, Board board, int depth, boolean nextIsMaxNode, double alpha, double beta) {
		numNodes++; 
		// siamo in un nodo CHANCE
		if (board.getBoardType()!=BoardType.CHANCE) {
			throw new RuntimeException("star1() e' richiamabile solo su nodi "+BoardType.CHANCE+", ma era "+board.getBoardType());
		}

		if (!silentDebug) System.out.println(tabs(depth)+"nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": entro nel sottolivello");
		if (!silentDebug) System.out.println(tabs(depth)+"range dal livello superiore["+alpha+", "+beta+"]");
		
		if (board.isTerminal() || depth<=0) {
			double ret= eval.evaluate(board, !nextIsMaxNode);
			if (!silentDebug) System.out.println(tabs(depth)+"nodo terminale "+ret);
			numEval++;
			return ret;
		}
		
		List<? extends ChanceEvent> events= board.chanceEvents();
		
		double N = events.size();
		double X = 0; // predecessor_scores
		double Y = 1; // succ_prob

		double vsum=0;
		
		int moveInd=0;
		int moveSize= events.size();
		for (ChanceEvent ev : events) {
			moveInd++;
			
			// aggiorno solo Y
			Y= Y-ev.probability();
			
			double A= (alpha-(eval.upperBound()*Y)-X)/ev.probability();
			double B= (beta -(eval.lowerBound()*Y)-X)/ev.probability();
			
			double AX = Math.max(A, eval.lowerBound());
			double BX = Math.min(B, eval.upperBound());

			if (!silentDebug) System.out.println(tabs(depth)+"range["+A+", "+B+"]");
			if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+(moveInd)+"/"+events.size()+") "+ev);
			
			Board succ= board.successor(ev);
			double v = alphaBeta(eval,succ,depth-1,nextIsMaxNode,AX,BX);
			vsum = vsum + ev.probability()*v; // somma pesata
			if (!silentDebug) System.out.println(tabs(depth)+"score ("+(moveInd)+"/"+events.size()+") "+ev+" = " + v);
			
			if(v<= A) {
				if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo aver valutato la mossa ("+(moveInd)+"/"+events.size()+") "+ev);
				
				double ret;
				
				if (!FAIL_SOFT) {
					
					// fail hard	
					ret= (alpha);
					
				} else {

					//fail soft
					// NB: moveInd e' nel range [1;N]
					Iterator<? extends ChanceEvent> iter= events.iterator();
					for (int i=1; i<=moveInd; i++) {
						iter.next();
					}
					double s=0.0;
					while (iter.hasNext()) {
						ChanceEvent ev2= iter.next();
						s+= eval.upperBound()*ev2.probability();
					}
					ret= vsum + s;
					
				}
				
				if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(ret));
				return ret;
				
			}
			if(v>= B) {
				if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo aver valutato la mossa ("+(moveInd)+"/"+events.size()+") "+ev);
				
				double ret;
				if (!FAIL_SOFT) {
					
					// fail hard	
					ret= (beta);
					
				} else {
				
					//fail soft
					// NB: moveInd e' nel range [1;N]
					Iterator<? extends ChanceEvent> iter= events.iterator();
					for (int i=1; i<=moveInd; i++) {
						iter.next();
					}
					double s=0.0;
					while (iter.hasNext()) {
						ChanceEvent ev2= iter.next();
						s+= eval.lowerBound()*ev2.probability();
					}
					ret= vsum + s;
				}
				if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(ret));
				return ret;
			}
			
			
			//aggiornamento solo X
			X= X+ev.probability()*v;
			
		}
		if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(vsum));
		return (vsum);
	}
	

	
	/**
	 * Star2, i nodi successivi sono nodi min
	 * @param eval euristica
	 * @param board stato
	 * @param depth profondita' di ricerca
	 * @return
	 */
	public static double star2min(Evaluator eval, Board board, int depth, double alpha, double beta) {
		numNodes++;
		// siamo in un nodo CHANCE
		if (board.getBoardType()!=BoardType.CHANCE) {
			throw new RuntimeException("star2min() e' richiamabile solo su nodi "+BoardType.CHANCE+", ma era "+board.getBoardType());
		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": entro nel sottolivello");
		if (!silentDebug) System.out.println(tabs(depth)+"range dal livello superiore["+alpha+", "+beta+"]");
		
		if (board.isTerminal() || depth<=0) {
			double ret= eval.evaluate(board, true); // il nodo precedente era di tipo MAX
			if (!silentDebug) System.out.println(tabs(depth)+"nodo terminale "+ret);
			numEval++;
			return ret;
		}
		
		List<? extends ChanceEvent> events= board.chanceEvents();
		
		double N = events.size();
		
		// range initialization

		double X = 0; // predecessor_scores
		double Y = 1; // succ_prob
		
		double []w= new double[(int)N]; // array di upper bound
		
		// probing phase
		if (!silentDebug) System.out.println(tabs(depth)+"Inizio della fase di probing");
		int i=0;
		double wsum= 0;
		
		double A, AX;
		ChanceEvent firstEv= events.get(0);
		double B= (beta - eval.lowerBound()*(1-firstEv.probability()) ) / firstEv.probability();
		double BX= Math.min(B, eval.upperBound());
		
		for (ChanceEvent ev : events) {
			
			if (DISABLE_PROBING_AB && DISABLE_PROBING_CUTOFF) break; // disabilita probing
			
			// aggiorno solo Y
			Y= Y-ev.probability();

			A= (alpha-(eval.upperBound()*Y)-X)/ev.probability();
			AX = Math.max(A, eval.lowerBound());

			if (!silentDebug) System.out.println(tabs(depth)+"range probing["+A+", "+B+"]");
			
			if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+(i+1)+"/"+events.size()+") "+ev);
			
			Board succ= board.successor(ev);
			double score= probe(eval, succ, depth-1, false, AX, BX); // il prossimo nodo e' MIN
			w[i]= score*ev.probability();
			wsum+= w[i];

			if (!silentDebug) System.out.println(tabs(depth)+"probe ("+(i+1)+"/"+events.size()+") "+ev+" = " + score);
			if (!silentDebug) System.out.println(tabs(depth)+"w[]="+Arrays.toString(w));
			
			if (!DISABLE_PROBING_CUTOFF && score <= A) {
				
				if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo il probe della mossa ("+(i+1)+"/"+events.size()+") "+ev);
				
				double ret;
				if (!FAIL_SOFT) {
					
					// fail hard	
					ret= (alpha);
					
				} else {

					//fail soft
					Iterator<? extends ChanceEvent> iter= events.iterator();
					int moveInd= i+1; // range [1;N]
					for (int k=1; k<=moveInd; k++) {
						iter.next();
					}
					double s=0.0;
					while (iter.hasNext()) {
						ChanceEvent ev2= iter.next();
						s+= eval.upperBound()*ev2.probability();
					}
					ret= wsum + s;
					
				}
				
				if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(ret));
				return ret;
			}
			
			//aggiornamento solo X
			X= X+ev.probability()*score;
			
			// aggiorno indice di "w"
			i++;

		}
		
		// range initialization
		X = 0; // predecessor_scores
		Y = 1; // succ_prob
		
		// search phase
		if (!silentDebug) System.out.println(tabs(depth)+"Inizio della fase di search");
		double vsum=0;
		
		i= 0;
		for (ChanceEvent ev : events) {
			// aggiorno solo Y
			Y= Y-ev.probability();
			
			//A= (alpha-(eval.upperBound()*Y)-X)/ev.probability(); // XXX pare sbagliato: bisogna calcolare B
			B= (beta -(eval.lowerBound()*Y)-X)/ev.probability();
			
			// XXX si potrebbe calcolare questa somma in modo incrementale
			// calcolo di A in modo iterativo
			//double h= 0;
			//for (int k=i+1; k<w.length; k++) h+= w[k];
			//A= (alpha -h -X)/ev.probability();
			// calcolo di A in modo incrementale
			wsum-= w[i]; // cur_w
			A= (alpha -wsum -X)/ev.probability();

			if (DISABLE_PROBING_AB) {
				A= (alpha-(eval.upperBound()*Y)-X)/ev.probability();
				B= (beta -(eval.lowerBound()*Y)-X)/ev.probability();	
			}
			
			AX = Math.max(A, eval.lowerBound());
			BX = Math.min(B, eval.upperBound());
			
			if (!silentDebug) System.out.println(tabs(depth)+"range["+A+", "+B+"]");
			if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+(i+1)+"/"+events.size()+") "+ev);
			
			Board succ= board.successor(ev);
			double v= alphaBeta(eval, succ, depth-1, false, AX, BX); // il prossimo nodo e' MIN
			vsum+= v*ev.probability();
			if (!silentDebug) System.out.println(tabs(depth)+"search ("+(i+1)+"/"+events.size()+") "+ev+" = " + v);
			
			if (v <= A) {
				
				if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo aver valutato la mossa ("+(i+1)+"/"+events.size()+") "+ev);
				

				double ret;
				if (!FAIL_SOFT) {
					
					// fail hard	
					ret= (alpha);
					
				} else {

					//fail soft
					Iterator<? extends ChanceEvent> iter= events.iterator();
					int wIndex= -1;
					int moveInd= i+1; // range [1;N]
					for (int k=1; k<=moveInd; k++) {
						iter.next();
						wIndex++;
					}
					double s=0.0;
					while (iter.hasNext()) {
						ChanceEvent ev2= iter.next();
						//s+= eval.upperBound()*ev2.probability();
						s+= w[wIndex]; //XXX funzionera'?
					}
					ret= vsum + s;
					
				}
				if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(ret));
				return ret;
			}
			if (v >= B) {

				if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo aver valutato la mossa ("+(i+1)+"/"+events.size()+") "+ev);

				double ret;
				if (!FAIL_SOFT) {
					
					// fail hard	
					ret= (beta);
					
				} else {
				
					//fail soft
					Iterator<? extends ChanceEvent> iter= events.iterator();
					int moveInd= i+1; // range [1;N]
					for (int k=1; k<=moveInd; k++) {
						iter.next();
					}
					double s=0.0;
					while (iter.hasNext()) {
						ChanceEvent ev2= iter.next();
						s+= eval.lowerBound()*ev2.probability();
					}
					ret= vsum + s;
				}

				if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(ret));
				return ret;
			}
			
			//aggiornamento solo X
			X= X+ev.probability()*v;
			
			// aggiorno indice di "w"
			i++;
		}
		if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(vsum));
		return vsum;

	}
	

	/**
	 * Star2, i nodi successivi sono nodi max
	 * @param eval euristica
	 * @param board stato
	 * @param depth profondita' di ricerca
	 * @return
	 */
	public static double star2max(Evaluator eval, Board board, int depth, double alpha, double beta) {
		numNodes++;
		// siamo in un nodo CHANCE
		if (board.getBoardType()!=BoardType.CHANCE) {
			throw new RuntimeException("star2min() e' richiamabile solo su nodi "+BoardType.CHANCE+", ma era "+board.getBoardType());
		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": entro nel sottolivello");
		if (!silentDebug) System.out.println(tabs(depth)+"range dal livello superiore["+alpha+", "+beta+"]");
		
		if (board.isTerminal() || depth<=0) {
			double ret= eval.evaluate(board, false);  // il nodo precedente era di tipo MIN
			if (!silentDebug) System.out.println(tabs(depth)+"nodo terminale "+ret);
			numEval++;
			return ret;
		}
		
		List<? extends ChanceEvent> events= board.chanceEvents();
		
		double N = events.size();
		
		// range initialization
		double X = 0; // predecessor_scores
		double Y = 1; // succ_prob
		
		double []w= new double[(int)N]; // array di lower bound
		
		// probing phase
		if (!silentDebug) System.out.println(tabs(depth)+"Inizio della fase di probing");
		
		double B, BX;
		ChanceEvent firstEv= events.get(0);
		double A= (alpha - eval.upperBound()*(1-firstEv.probability()) ) / firstEv.probability(); // cur_alpha
		double AX= Math.max(A, eval.lowerBound()); // ax
		
		int i=0;
		double wsum= 0; // cur_w
		for (ChanceEvent ev : events) {
			
			if (DISABLE_PROBING_AB && DISABLE_PROBING_CUTOFF) break; // disabilita il probing
			
			// aggiorno solo Y
			Y= Y-ev.probability();

			B= (beta -(eval.lowerBound()*Y)-X)/ev.probability(); // cur_beta
			BX = Math.min(B, eval.upperBound()); // bx
			
			if (!silentDebug) System.out.println(tabs(depth)+"range probing["+A+", "+B+"]");
			
			if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+(i+1)+"/"+events.size()+") "+ev);
			
			Board succ= board.successor(ev);
			double score= probe(eval, succ, depth-1, true, AX, BX); // il prossimo nodo e' MAX
			w[i]= score*ev.probability();
			wsum+= w[i];
			if (!silentDebug) System.out.println(tabs(depth)+"probe ("+(i+1)+"/"+events.size()+") "+ev+" = " + score);
			if (!silentDebug) System.out.println(tabs(depth)+"w[]="+Arrays.toString(w));
			
			if (!DISABLE_PROBING_CUTOFF && score >= B) {

				if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo il probe della mossa ("+(i+1)+"/"+events.size()+") "+ev);
				double ret;
				
				if (!FAIL_SOFT) {
					
					// fail hard	
					ret= (beta);
					
				} else {
				
					//fail soft
					int moveInd= i+1; // range [1;N]
					Iterator<? extends ChanceEvent> iter= events.iterator();
					for (int k=1; k<=moveInd; k++) {
						iter.next();
					}
					double s=0.0;
					while (iter.hasNext()) {
						ChanceEvent ev2= iter.next();
						s+= eval.lowerBound()*ev2.probability();
					}
					ret= wsum + s;
				}
				if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(ret));
				return ret;
			}
			
			//aggiornamento solo X
			X= X+ev.probability()*score;
			
			// aggiorno indice di "w"
			i++;

		}
		
		// range initialization
		X = 0; // predecessor_scores
		Y = 1; // succ_prob
		
		// search phase
		if (!silentDebug) System.out.println(tabs(depth)+"Inizio della fase di search");
		double vsum=0;
		
		i= 0;
		for (ChanceEvent ev : events) {
			// aggiorno solo Y
			Y= Y-ev.probability();
			
			A= (alpha-(eval.upperBound()*Y)-X)/ev.probability();
			
			// XXX si potrebbe calcolare questa somma in modo incrementale
			// calcolo di B in modo iterativo
			//double h= 0;
			//for (int k=i+1; k<w.length; k++) h+= w[k];
			//B= (beta -h -X)/ev.probability();
			// calcolo di B in modo incrementale
			wsum-= w[i]; // cur_w
			B= (beta -wsum -X)/ev.probability();

			if (DISABLE_PROBING_AB) {
				A= (alpha-(eval.upperBound()*Y)-X)/ev.probability();
				B= (beta -(eval.lowerBound()*Y)-X)/ev.probability();
			}
			
			AX = Math.max(A, eval.lowerBound());
			BX = Math.min(B, eval.upperBound());

			if (!silentDebug) System.out.println(tabs(depth)+"range["+A+", "+B+"]");
			
			if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+(i+1)+"/"+events.size()+") "+ev);
			
			Board succ= board.successor(ev);
			double v= alphaBeta(eval, succ, depth-1, true, AX, BX); // il prossimo nodo e' MAX
			vsum+= v*ev.probability();
			if (!silentDebug) System.out.println(tabs(depth)+"search ("+(i+1)+"/"+events.size()+") "+ev+" = " + v);
			
			if (v <= A) {
				
				if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo aver valutato la mossa ("+(i+1)+"/"+events.size()+") "+ev);
				
				double ret;
				if (!FAIL_SOFT) {
					
					// fail hard	
					ret= (alpha);
					
				} else {

					//fail soft
					Iterator<? extends ChanceEvent> iter= events.iterator();
					int moveInd= i+1; // range [1;N]
					for (int k=1; k<=moveInd; k++) {
						iter.next();
					}
					double s=0.0;
					while (iter.hasNext()) {
						ChanceEvent ev2= iter.next();
						s+= eval.upperBound()*ev2.probability();
					}
					ret= vsum + s;
					
				}

				if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(ret));
				return ret;
			}
			if (v >= B) {

				if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo aver valutato la mossa ("+(i+1)+"/"+events.size()+") "+ev);

				double ret;

				if (!FAIL_SOFT) {
					
					// fail hard	
					ret= (beta);
					
				} else {
				
					//fail soft
					Iterator<? extends ChanceEvent> iter= events.iterator();
					int wIndex= -1;
					int moveInd= i+1; // range [1;N]
					for (int k=1; k<=moveInd; k++) {
						iter.next();
						wIndex++;
					}
					double s=0.0;
					while (iter.hasNext()) {
						ChanceEvent ev2= iter.next();
						//s+= eval.lowerBound()*ev2.probability();
						s+= w[wIndex]; // XXX funzionera' correttamente?
					}
					ret= vsum + s;
				}
				
				if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(ret));
				return ret;
			}
			
			
			//aggiornamento solo X
			X= X+ev.probability()*v;
			
			// aggiorno indice di "w"
			i++;
		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(vsum));
		return vsum;

	}
	
	private static double probe(Evaluator eval, Board board, int depth, boolean isMaxNode, double alpha, double beta) {
		numNodes++;
		// siamo in un nodo MIN/MAX
		if (board.getBoardType()==BoardType.CHANCE) {
			throw new RuntimeException("probeMin() e' richiamabile solo su nodi "+BoardType.MIN+" o "+BoardType.MAX+", ma era "+board.getBoardType());
		}
		
		else if (isMaxNode && board.getBoardType()!=BoardType.MAX) {
			throw new RuntimeException("probe() si aspettava un nodo "+BoardType.MAX+", ma era "+board.getBoardType());
		}
		
		else if (!isMaxNode && board.getBoardType()!=BoardType.MIN) {
			throw new RuntimeException("probe() si aspettava un nodo "+BoardType.MIN+", ma era "+board.getBoardType());
		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": entro nel sottolivello (probing di questo nodo)");
		if (!silentDebug) System.out.println(tabs(depth)+"range dal livello superiore["+alpha+", "+beta+"]");
		
		if (board.isTerminal() || depth<=0) {
			double ret= eval.evaluate(board, isMaxNode);
			if (!silentDebug) System.out.println(tabs(depth)+"nodo terminale "+ret);
			numEval++;
			return ret;
		}
		MoveEvent choice= pickSuccessor(eval, board);
		if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa restituita da pickSuccessor "+choice);
		Board succ= board.successor(choice);
		
		if (isMaxNode) {
			double score= star2min(eval, succ, depth-1, alpha, beta);
			if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+score);
			return score;
		} else {
			double score= star2max(eval, succ, depth-1, alpha, beta);
			if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+score);
			return score;
		}
	}
	
	private static MoveEvent pickSuccessor(Evaluator eval, Board board) {
		//numNodes++; // con l'implementazione attuale di pickSuccessor non viene visitato alcun nodo
		// siamo in un nodo MIN/MAX
		if (board.getBoardType()==BoardType.CHANCE) {
			throw new RuntimeException("pickSuccessor() e' richiamabile solo su nodi "+BoardType.MIN+" o "+BoardType.MAX+", ma era "+board.getBoardType());
		}
		
		boolean isMaxNode;
		if (board.getBoardType()==BoardType.MAX) isMaxNode= true;
		else isMaxNode= false;
		
		List<? extends MoveEvent> events= board.moveEvents(eval);
		
		/*
		 * Dal momento che le mosse sono gia' ordinate e che utilizziamo la stessa
		 * euristica sia per l'ordinamento delle mosse che nella fase di probing
		 * (funzioni goodQuality/bestQuality) la prima mossa e' sicuramente quella
		 * migliore.
		 */
		return events.get(0); // restituisco il primo elemento
		
		/*
		if (events.size()<2) {
			return events.get(0); // un solo elemento
		} else {
			// almeno due elementi
			
			MoveEvent choice= events.get(0);
			
			for (MoveEvent m : events) {
				numNodes++;
				
				Board succ= board.successor(m);
				
				if (eval.hasBestQuality(succ, isMaxNode)) {
					numEval++;
					return m;
				} else if (eval.hasGoodQuality(succ, isMaxNode)) {
					numEval++;
					choice= m;
				}
			}
			
			return choice;
		}
		*/

	}
	
	
	public static double minimax(Evaluator eval, Board board, int depth, boolean thisIsMaxNode) {
		numNodes++;
		// siamo in un nodo MIN/MAX
		if (board.getBoardType()==BoardType.CHANCE) {
			throw new RuntimeException("chanceMinimax() e' richiamabile solo su nodi "
					+BoardType.MIN+" o "+BoardType.MAX+", ma era "+board.getBoardType());
		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": entro nel sottolivello");

		if (board.isTerminal() || depth<=0) {
			double ret= eval.evaluate(board, thisIsMaxNode);
			if (!silentDebug) System.out.println(tabs(depth)+"nodo terminale "+ret);
			numEval++;
			return ret;
		}
		
		List<? extends MoveEvent> events= board.moveEvents(eval);
		//System.out.println("Branching factor min/max: "+events.size());
		double score;
		
		if (thisIsMaxNode) {
			
			// massimizzare
			score= Double.NEGATIVE_INFINITY;

			int moveInd=0;
			int moveSize= events.size();
			for (MoveEvent ev : events) {
				moveInd++;

				if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+(moveInd)+"/"+events.size()+") "+ev);
				
				Board succ= board.successor(ev);
				double v= expectimax(eval, succ, depth-1, !thisIsMaxNode);
				if (v>score) score = v;
				if (!silentDebug) System.out.println(tabs(depth)+"score ("+(moveInd)+"/"+events.size()+") "+ev+" = " + v);
			}
			
		} else {

			// minimizzare
			score= Double.POSITIVE_INFINITY;
			
			int moveInd=0;
			int moveSize= events.size();
			for (MoveEvent ev : events) {
				moveInd++;
				
				if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+(moveInd)+"/"+events.size()+") "+ev);
				
				Board succ= board.successor(ev);
				double v= expectimax(eval, succ, depth-1, !thisIsMaxNode);
				if (v<score) score = v;
				if (!silentDebug) System.out.println(tabs(depth)+"score ("+(moveInd)+"/"+events.size()+") "+ev+" = " + v);
			}

		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+(score));

		return score;
	}
	
	/**
	 * con alpha-beta
	 * @param eval
	 * @param board
	 * @param depth
	 * @param thisIsMaxNode
	 * @return
	 */
	public static double alphaBeta(Evaluator eval, Board board, int depth, boolean thisIsMaxNode,double alpha, double beta) {
		numNodes++;
		// siamo in un nodo MIN/MAX
		if (board.getBoardType()==BoardType.CHANCE) {
			throw new RuntimeException("chanceMinimax() e' richiamabile solo su nodi "
					+BoardType.MIN+" o "+BoardType.MAX+", ma era "+board.getBoardType());
		}
		
		if (!silentDebug) System.out.println(tabs(depth)+"nodo="+board+", tipo="+board.getBoardType()+", depth="+depth+": entro nel sottolivello");
		if (!silentDebug) System.out.println(tabs(depth)+"range dal livello superiore["+alpha+", "+beta+"]");
		
		if (board.isTerminal() || depth<=0) {
			double ret= eval.evaluate(board, thisIsMaxNode);
			if (!silentDebug) System.out.println(tabs(depth)+"nodo terminale "+ret);
			numEval++;
			return ret;
		}
		
		List<? extends MoveEvent> events= board.moveEvents(eval);

		double score;
		
		if (thisIsMaxNode) {
			
			// massimizzare
			score= Double.NEGATIVE_INFINITY;
			
			int moveInd=0;
			int moveSize= events.size();
			for (MoveEvent ev : events) {
				moveInd++;
				
				if (!silentDebug) System.out.println(tabs(depth)+"range["+alpha+", "+beta+"]");
				
				if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+moveInd+"/"+moveSize+") "+ev);
				Board succ= board.successor(ev);
				double v;
				if (STAR2) {
					// thisIsMaxNode==true
					v= star2min(eval, succ, depth-1, alpha, beta);
				} else {
					v= star1(eval, succ, depth-1, !thisIsMaxNode,alpha,beta);
				}
				
				if(v>=beta){
					score=v;
					if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo aver valutato la mossa ("+moveInd+"/"+moveSize+") "+ev);
					break;
				}
				else if (v>score) score = v;
				
				if (v > alpha) {
					alpha= v; // aggiorno alpha con il maggiore fra "alpha" e "v"
					if (!silentDebug) System.out.println(tabs(depth)+"aggiornato alpha="+alpha);
				}
			}
			
		} else {

			// minimizzare
			score= Double.POSITIVE_INFINITY;
			
			int moveInd=0;
			int moveSize= events.size();
			for (MoveEvent ev : events) {
				moveInd++;
				
				if (!silentDebug) System.out.println(tabs(depth)+"range["+alpha+", "+beta+"]");
				
				if (!silentDebug) System.out.println(tabs(depth)+"eseguo mossa ("+moveInd+"/"+moveSize+") "+ev);
				Board succ= board.successor(ev);
				double v;
				if (STAR2) {
					// thisIsMaxNode==false
					v= star2max(eval, succ, depth-1, alpha, beta);
				} else {
					v= star1(eval, succ, depth-1, !thisIsMaxNode,alpha,beta);
				}
				if(v<=alpha){
					score=v;
					if (!silentDebug) System.out.println(tabs(depth)+"taglio dopo aver valutato la mossa ("+moveInd+"/"+moveSize+") "+ev);
					break;
				}
				else if (v<score) score = v;
				
				if (v < beta) {
					beta= v; // aggiorno beta con il maggiore fra "beta" e "v"
					if (!silentDebug) System.out.println(tabs(depth)+"aggiornato beta="+beta);
				}
			}

		}
		if (!silentDebug) System.out.println(tabs(depth)+"lo score calcolato e' "+score);
		return score;
	}

	
	////////////////////////////////////////////////////////////////////////////
	// STATISTICHE
	
	public static void resetStats() {
		maxTimeStat.clear();
		minTimeStat.clear();
		maxNodesStat.clear();
		minNodesStat.clear();
	}

	/**
	 * L'unita' di misura e' ns
	 * @return
	 */
	public static Vector<Long> getMaxTimeStat() {
		return maxTimeStat;
	}
	
	/**
	 * L'unita' di misura e' ns
	 * @return
	 */
	public static Vector<Long> getMinTimeStat() {
		return minTimeStat;
	}
	
	/**
	 * L'unita' di misura e' ms
	 * @param isMax
	 * @return
	 */
	public static double meanTime(boolean isMax) {
		Vector<Long> stats;
		if (isMax) stats= maxTimeStat;
		else stats= minTimeStat;
		
		double sum = 0;
		for (Long l : stats) {
			sum += l;
		}
		
		return (sum / (double)stats.size()) / 1000000.0; // conversione ns -> ms
	}
	
	public static Vector<Long> getMaxNodesStat() {
		return maxNodesStat;
	}
	
	public static Vector<Long> getMinNodesStat() {
		return minNodesStat;
	}
	
	public static double meanNodes(boolean isMax) {
		Vector<Long> stats;
		if (isMax) stats= maxNodesStat;
		else stats= minNodesStat;
		
		double sum = 0;
		for (Long l : stats) {
			sum += l;
		}
		
		return (sum / (double)stats.size());
	}
	
	/**
	 * Quando e' impostato come "silente", non stampa output "verboso"
	 * @param silent
	 */
	public static void setSilentDebug(boolean silent) {
		Search.silentDebug= silent;
	}
	/**
	 * Quando e' impostato come "silente", non stampa alcun tipo di output
	 * @param silent
	 */
	public static void setSilent(boolean silent) {
		Search.silent= silent;
		if (silent) silentDebug= true;
	}
}
